//单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足： 
//
// 
// words.length == indices.length 
// 助记字符串 s 以 '#' 字符结尾 
// 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 
//words[i] 相等 
// 
//
// 给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。 
//
// 
//
// 示例 1： 
//
// 
//输入：words = ["time", "me", "bell"]
//输出：10
//解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
//words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
//words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
//words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
// 
//
// 示例 2： 
//
// 
//输入：words = ["t"]
//输出：2
//解释：一组有效编码为 s = "t#" 和 indices = [0] 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= words.length <= 2000 
// 1 <= words[i].length <= 7 
// words[i] 仅由小写字母组成 
// 
//
// 
//
// 
// 注意：本题与主站 820 题相同： https://leetcode-cn.com/problems/short-encoding-of-words/ 
//
// Related Topics 字典树 数组 哈希表 字符串 👍 50 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-02-26 23:31:17
 * @description LCR 065.单词的压缩编码
 */
public class ISwD2y{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ISwD2y fun=new ISwD2y();
	 	 Solution solution = fun.new Solution();
		solution.minimumLengthEncoding(new String[]{"time","atime","btime"});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //因为题目长度限制，所以每个单词最多有7个后缀，遍历每个单词，删除所有后缀，每个单词需要一个 #，加起来返回
	public int minimumLengthEncoding1(String[] words) {
		Set<String> good = new HashSet<String>(Arrays.asList(words));
		for (String word: words) {
			for (int k = 1; k < word.length(); ++k) {
				good.remove(word.substring(k));
			}
		}

		int ans = 0;
		for (String word: good) {
			ans += word.length() + 1;
		}
		return ans;
	}
	//对每个单词，找到他的结尾，如果这个单词没有子节点了，则他的前缀都可以用他计数
	//找到所有没有子节点的单词
    public int minimumLengthEncoding(String[] words) {
		Map<Trie,Integer> map=new HashMap<>();
		Trie a=new Trie();
		for (String word : words) {
			Trie cur=a;
			for (int length = word.length()-1; length >=0; length--) {
				cur=cur.get(word.charAt(length));
			}
			map.put(cur,word.length());
		}
		return map.entrySet().stream().filter(entry->!entry.getKey().hasNe).mapToInt(entry->entry.getValue()+1).sum();
    }
	class Trie{
		Trie[] ne;
		boolean hasNe;
		Trie(){
			ne=new Trie[26];
			hasNe=false;

		}
		Trie get(char  c){
			if(ne[c-'a']==null){
				ne[c-'a']=new Trie();
				hasNe=true;
			}
			return ne[c-'a'];
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
